package org.raymond.iworks.study.basic.structure.tree.huffman;

import java.util.*;

/**
 * 赫夫曼编码,是一种编码方式,属于一种程序算法
 * 赫夫曼编码是赫夫曼树在电讯通信中的经典应用之一
 * 赫夫曼编码广泛应用于数据文件压缩,其压缩率通常在20%~90%之间
 * 赫夫曼码是可变字长编码(VLC)的一种.Huffman于1952年提出一种编码方法,称之为最佳编码
 *
 * 原理剖析
 * 通信领域中信息的处理方式1-定长编码
 * I like like like java do you like a java //共40个字符(包括空格)
 * ASCII编码 ...
 * 二进制编码 ...
 * 按照二进制来传递信息,总长度是311(包括空格)
 *
 * 通信领域中信息的处理方式2-变长编码
 * d:1 y:1 u:1 j:2 v:2 o:2 l:4 k:4 e:4 i:5 a:5 " ":9 //各个字符对应的个数
 * 0= ,1=a,10=j,11=e,100=k,101=l,110=o,111=v,1000=j,1001=u,1010=y,1011=d
 * 说明:按照各个字符出现的次数进行编码,原则是出现次数越多的,则编码越小,比如空格出现了9次,
 * 编码为0,其他依次类推.
 *
 * 按照上面给各个字符规定的编码,则我们在传输"i like like like java do you like a java"
 * 数据时,编码就是 10 0 101 10 100 ...
 * 注:这只是一个简单示例,其实是有问题的,不是前缀编码,识别的时候会有多义性.
 * 如第一个单词是1,还是10,还是100?
 * 字符的编码都不能是其他字符编码的前缀,符合此要求的编码叫做前缀编码,即不能匹配到重复的编码.
 *
 * 通信领域中信息的处理方式3-赫夫曼编码
 * 1) 初始化字符串
 * 2) 统计各个字符出现的次数
 * d:1 y:1 u:1 j:2 v:2 o:2 l:4 k:4 e:4 i:5 a:5 " ":9 //各个字符对应的个数
 * 3) 按照上面字符出现的次数构建一颗赫夫曼树,次数作为权值
 * 4) 根据赫夫曼树,给各个字符规定编码,向左的路径为0,向右的路径为1,编码即路径,编码如下:
 * o=1000,u=10010,d=100110,y=100111,i=101,a=110,k=1110,e=1111,j=0000,
 * v=0001,l=001," "=01
 *
 * 按照上面的赫夫曼编码,字符串对应的编码为(无损压缩)...
 * 长度为:133
 * 说明:
 * 1) 原来长度是311，压缩了(311-133)/311=57.23%
 * 2) 此编码满足前缀编码,即字符的编码都不能是其他字符编码的前缀.不会造成匹配多义性.
 * 注意,这个赫夫曼树根据排序方法不同,也可能不太一样,这样对应的赫夫曼编码也不完全一样,但是
 * wpl是一样的,都是最小的.比如:如果我们让每次生成的新的二叉树总是排序在权值相同的二叉树的
 * 最后一个,则生成的赫夫曼树与之前的也不一样.(赫夫曼树的不稳定性,可能生成权值相同的节点,
 * 而新生成的权值相同的节点的放置位置没有规定)
 *
 * 最佳实践-数据压缩(创建赫夫曼树)
 * 将给出的一段文本,根据赫夫曼编码原理,对其进行数据压缩处理
 * 1) 根据赫夫曼编码压缩数据的原理,需要创建给定文本对应的赫夫曼树
 * 思路:
 * 1) Node { data(存放数据), weight(权限), left和right }
 * 2) 得到 "i like like like java do you like a java" 对应的byte[]数组
 * 3) 编写一个方法,将准备构建赫夫曼树的node节点放到list中,形式为
 * [Node[data=97,weight=5],Node[data=32,weight=9]...],体现
 *  d:1 y:1 u:1 j:2 v:2 o:2 l:4 k:4 e:4 i:5 a:5 " ":9
 * 4) 可以通过List创建对应的赫夫曼树
 *
 * 最佳实践-数据压缩(生成赫夫曼编码和赫夫曼编码后的数据)
 * 1) 生成赫夫曼树对应的赫夫曼编码
 * " "=01,a=100,d=11000,u=11001,e=1110,v=11011,i=101,y=11010,j=0010,k=1111,
 * l=000,o=0011,
 * 2) 使用赫夫曼编码来生成赫夫曼编码数据,即按照上面的赫夫曼编码,将 源字符串 转成对应的
 * 编码数据
 * 最佳实践-数据解压(使用赫夫曼编码解码)
 * 1) 对之前得到的赫夫曼编码和压缩后的数据进行解压
 * 2) 重新得到原来的字符串
 *
 * 注意事项:
 * 1) 如果文件本身就是经过压缩处理的,那么使用赫夫曼编码再压缩效率不会有明显变化,
 * 比如视频,ppt等文件
 * 2) 赫夫曼编码是按字节来处理的,因此可以处理所有的文件(二进制文件,文本文件)
 * 3) 如果一个文件中的内容,重复的数量不多,压缩效果也不会很明显
 */
public class HuffmanCodeDemo {
    public static void main(String[] args) {
        // String s = "i like like like java do you like a java you are lihai";
        String s = "i like like like java do you like a java";
        // fixCode(s);
        byte[] sBytes = s.getBytes();
        // 压缩
        byte[] zipped = huffmanzip(sBytes);
        System.out.println("压缩前长度:"+sBytes.length+"\n压缩后长度:"+zipped.length);

        //
        int i = Integer.parseInt("010", 2);
        byte b = (byte)i;
        System.out.println(i+"-"+byte2BitString(false, b));

        // 解压
        byte[] result = decode(huffmanCodes, zipped);
        System.out.println(new String(result));
    }

    /**
     *
     * @param huffmanCodes
     * @param huffmanBytes
     * @return
     */
    private static byte[] decode(Map<Byte, String> huffmanCodes, byte[] huffmanBytes){
        // 先得到huffmanBytes对应的二进制字符串
        StringBuilder sb = new StringBuilder();
        // 将byte[]转成二进制字符串
        // todo
        // 如果huffmanBytes中最后一个是负数,说明8位一定是占满了.
        // 如果是负数,不管是不是最后一位都要截取,
        // 如果是正数,不是最后一位需要补高位,是最后一位则直接返回.因为正数在byte范围内最大是 111 1111
        for(int i=0; i<huffmanBytes.length; i++){
            byte b = huffmanBytes[i];
            // 判断是不是最后一个字节
            boolean flag = (i==huffmanBytes.length-1);
            sb.append(byte2BitString(!flag, b));
        }
        // 把字符串按照指定的赫夫曼编码进行解码
        // 把赫夫曼编码表进行调换,因为反向查询a->100,100->a
        Map<String, Byte> map = new HashMap<>();
        for(Map.Entry<Byte, String> entry : huffmanCodes.entrySet()) {
            map.put(entry.getValue(), entry.getKey());
        }

        List<Byte> list = new ArrayList<>();
        for(int i=0; i<sb.length();){
            // 获取编码的计数器
            int count=1;
            boolean flag = true;
            Byte b = null;
            while(flag){
                // 在while里,i不动,让count移动,直到取到匹配的字节
                String key = sb.substring(i, i+count);
                b = map.get(key);
                if(b==null){
                    // 还没匹配到,移动count
                    count++;
                }else{
                    // 匹配到
                    flag=false;
                }
            }
            list.add(b);
            // i直接移动到count
            i += count;
        }
        // 当for循环结束后,list中就存放了所有的byte
        byte[] b = new byte[list.size()];
        for(int i=0; i<b.length; i++){
            b[i]=list.get(i);
        }
        return b;
    }

    /**
     * 将一个byte转成一个二进制的字符串
     * @param flag 标识是否需要补高位,但最后一个byte不需要补高位
     * @param b
     * @return
     */
    private static String byte2BitString(boolean flag, byte b){
        // 将byte转为int
        int temp = b;
        if(flag) {
            // 补高位 按位或, 256=1000 0000
            temp |= 256;
        }
        String s = Integer.toBinaryString(temp);
        if(flag){
            return s.substring(s.length()-8);
        }else{
            return s;
        }
    }

    public static byte[] huffmanzip(byte[] original){
        List<CodeNode> nodes = nodes(original);
        CodeNode root = createHuffmanTree(nodes);
        // preOrder(root);
        // System.out.println("=========");

        // 生成赫夫曼编码
        buildHuffmanCodes(root);
        // System.out.println("赫夫曼编码:"+huffmanCodes);
        // 压缩
        byte[] zipped = zip(original, huffmanCodes);
        return zipped;
    }

    /**
     *
     * @param original  原始字符串对应的byte[]
     * @param huffmanCodes 已生成的赫夫曼编码 字符串
     * @return 被赫夫曼编码后字符串的byte[]
     * 即二进制字符串转换为二进制字节数组,即将字符串中每8位转为一个byte
     */
    private static byte[] zip(byte[] original, Map<Byte, String> huffmanCodes){
        StringBuilder sb = new StringBuilder();
        for(byte b : original){
            sb.append(huffmanCodes.get(b));
        }
        int len = (sb.length()+7)/8;
        /*
        if(sb.length()%8==0){
            len = sb.length()/8;
        }else{
            len = sb.length()/8+1;
        }*/
        // 存储压缩后的byte数组
        byte[] zipped = new byte[len];
        int index=0;
        for(int i=0; i<sb.length(); i+=8){
            String strBytes = null;
            if(i+8>sb.length()){
                strBytes = sb.substring(i);
                // 最后一位刚好8位说明有可能是负数,不到8位则是正数,需要特殊处理
                // todo
            }else {
                strBytes = sb.substring(i, i + 8);
            }
            // 将strBytes转换为二进制,并存入zipped
            zipped[index] = (byte)Integer.parseInt(strBytes, 2);
            index++;
        }

        return zipped;
    }

    /**
     * 生成赫夫曼树对应的赫夫曼编码
     * 思路:
     * 1,将赫夫曼编码表存放在Map<Byte,String> 形式
     * 2,在生成赫夫曼编码表时,需要拼接路径,以得到某个叶子节点的路径,存入一个StringBuilder
     */
    private static Map<Byte,String> huffmanCodes = new HashMap<>();
    private static StringBuilder stringBuilder = new StringBuilder();

    private static Map<Byte, String> buildHuffmanCodes(CodeNode root){
        if(root==null){
            return null;
        }
        // 注意,root的data为空,所以这里就省略对data的判断了
        buildHuffmanCodes(root.left, "0", stringBuilder);
        buildHuffmanCodes(root.right, "1", stringBuilder);
        return huffmanCodes;
    }

    /**
     * 根据传入的node结点生成对应的huffman编码
     * @param node
     * @param code 路径,左子结点为0,右子结点为1
     * @param inputSb
     */
    private static void buildHuffmanCodes(CodeNode node, String code, StringBuilder inputSb){
        StringBuilder sb = new StringBuilder(inputSb);
        sb.append(code);
        if(node==null){
            // 如果node==null,不处理
            return;
        }
        //判断当前node是叶子结点还是非叶子结点
        // 非叶子结点
        if(node.data==null){
            //递归处理
            //向左递归
            buildHuffmanCodes(node.left, "0", sb);
            //向右递归
            buildHuffmanCodes(node.right, "1", sb);
        // 叶子结点
        }else{
            // 表示找到了某个叶子结点的最后
            huffmanCodes.put(node.data, sb.toString());
        }
    }
    private static void preOrder(CodeNode node){
        if(node!=null){
            node.preOrder();
        }else{
            System.out.println("赫夫曼树为空,无法遍历");
        }
    }

    public static CodeNode createHuffmanTree(List<CodeNode> nodes) {
        while(nodes.size()>1) {
            // 排序,从小到大
            Collections.sort(nodes);
            // 取出权值最小的两颗二叉树
            CodeNode left = nodes.get(0);
            CodeNode right = nodes.get(1);
            // 构建新的二叉树,它的根节点没有data,只有权值
            CodeNode parent = new CodeNode(null, left.weight + right.weight);
            parent.left = left;
            parent.right = right;

            // 清理的是list中对元素的引用,但构建的树依然存在着
            nodes.remove(left);
            nodes.remove(right);
            nodes.add(parent);
        }
        return nodes.get(0);
    }

    private static List<CodeNode> nodes(byte[] bytes){
        List<CodeNode> nodes = new ArrayList<>();
        Map<Byte,Integer> countMap = new HashMap<>();
        for(byte b:bytes){
            countMap.merge(b,1,Integer::sum);
        }
        // 把每一个键值对转成一个CodeNode对象,并加入nodes
        countMap.forEach((k,v)->nodes.add(new CodeNode(k,v)));
        return nodes;
    }

    public static void fixCode(String s){
        StringBuilder ascii = new StringBuilder();
        StringBuilder binary = new StringBuilder();
        for(char c : s.toCharArray()){
            ascii.append((int)c+" ");
        }
        for(byte b : s.getBytes()){
            binary.append(Integer.toBinaryString(b&0xff)+" ");
        }
        System.out.println("ascii lenth:"+ascii.toString().length());
        System.out.println("binary lenth:"+binary.toString().length());
        // System.out.println("ascii:"+ascii);
        //System.out.println("binary:"+binary);
    }
}

class CodeNode implements Comparable<CodeNode>{
    // 存放数据本身,比如'a'=>97,' '=>32
    Byte data;
    // 权值,此处是data出现的次数
    int weight;
    CodeNode left;
    CodeNode right;
    public CodeNode(Byte data, int weight) {
        this.data = data;
        this.weight = weight;
    }

    @Override
    public int compareTo(CodeNode o) {
        return this.weight-o.weight;
    }

    @Override
    public String toString() {
        return "Node[data="+data+", weight="+weight+"]";
    }
    public void preOrder(){
        System.out.println(this);
        if(this.left!=null){
            this.left.preOrder();
        }
        if(this.right!=null){
            this.right.preOrder();
        }
    }
}

